438D - The Child and Sequence - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define CherryFrog ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

const int N = 5e5 + 9;
ll a[N];
struct ST {
  #define lc (n << 1)
  #define rc ((n << 1) + 1)
  long long  lazy[4 * N];

  struct tree
  {
      ll mx=0,sum=0;
  }t[N*4];

  ST() {
    //memset(t, 0, sizeof t);
    memset(lazy, 0, sizeof lazy);
  }
  inline long long combine(long long a,long long b) {
    return a + b;
  }
  inline void pull(int n) {
    t[n].sum = t[lc].sum + t[rc].sum;
    t[n].mx = max(t[lc].mx,t[rc].mx);
  }

  /* inline void push(int n, int b, int e) {
    if (lazy[n] == 0) return;
    if(t[n].mx<lazy[n])return ;
    if(b == e) t[n].sum = t[n].sum % lazy[n] ,t[n].mx = t[n].sum;
    if (b != e) {
       int mid = (b + e) >> 1;
       lazy[lc] = lazy[n];
       push(lc,b,mid);
       lazy[rc] = lazy[n];
       push(rc,mid+1,e);
    }
    lazy[n] = 0;
  }*/

  void build(int n, int b, int e) {
   // lazy[n] = 0;
    if (b == e) {
      t[n].sum = a[b];
      t[n].mx = a[b];
      return;
    }
    int mid = (b + e) >> 1;
    build(lc, b, mid);
    build(rc, mid + 1, e);
    pull(n);
  }
  void upd(int n, int b, int e, int i, int j, long long v) {
  //  push(n, b, e);
    if (j < b || e < i) return;
    if (i <= b && e <= j) {
      if(t[n].mx < v)return ;
      if( b== e)
      {
          t[n].sum = t[n].sum % v;
          t[n].mx = t[n].sum;
          return ;
       }
    }
    int mid = (b + e) >> 1;
    upd(lc, b, mid, i, j, v);
    upd(rc, mid + 1, e, i, j, v);
    pull(n);
  }

  void upd2(int n, int b, int e, int i, long long v) {
  //  push(n, b, e);
    if (i < b || e < i) return;
    if (b == e && b == i) {
       t[n].mx = v;
       t[n].sum = v;
      return;
    }
    int mid = (b + e) >> 1;
    upd2(lc, b, mid, i,  v);
    upd2(rc, mid + 1, e, i, v);
    pull(n);
  }

  long long query(int n, int b, int e, int i, int j) {
   // push(n, b, e);
    if (i > e || b > j) return 0;
    if (i <= b && e <= j) return t[n].sum;
    int mid = (b + e) >> 1;
    return combine(query(lc, b, mid, i, j), query(rc, mid + 1, e, i, j));
  }
}t;


void solve()
{
  int n,m;
  cin>>n>>m;

  for(int i=1;i<=n;i++)cin>>a[i];

  t.build(1,1,n);

  while(m--)
  {
      int id;
      cin>>id;

      if(id == 1)
      {
        int l,r;
        cin>>l>>r;
        cout << t.query(1,1,n,l,r) <<endl;
      }
      else if(id == 2)
      {
          int l,r;
          cin>>l>>r;
          ll x;
          cin>>x;
          t.upd(1,1,n,l,r,x);
      }
      else
      {
          int d;
          ll x;
          cin>>d>>x;
          t.upd2(1,1,n,d,x);
      }
  }

}

int main()
{
    CherryFrog;
  // int q;cin>>q;while(q--)solve();
  solve();
}